# 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
#
#  示例 1:
# 输入: [1,2,3,null,5,null,4]
# 输出: [1,3,4]
#
#  示例 2:
# 输入: [1,null,3]
# 输出: [1,3]
from com.example.tree.tree_node import TreeNode
from typing import List


class Solution:
    def rightSideView2(self, root: TreeNode) -> List[int]:
        """
        前序遍历(深度优先): 根 -> 右 -> 左的顺序能保证每一层第一个元素一定是该层的最右边的那个元素
        :param root:
        :return:
        """
        if not root:
            return []
        stack = [(root, 0)]
        dic = {}  # key:二叉树的层数 value: 该层最右边元素的val值
        maxDepth = -1
        while stack:
            tmp, depth = stack.pop()
            maxDepth = max(depth, maxDepth)
            dic.setdefault(depth, tmp.val)  # 如果不存在对应深度的节点才插入
            if tmp.left:
                stack.append((tmp.left, depth + 1))  # 子节点的层数为当前节点的层数 + 1
            if tmp.right:
                stack.append((tmp.right, depth + 1))  # 子节点的层数为当前节点的层数 + 1
        return list(dic.values())

    def rightSideView1(self, root: TreeNode) -> List[int]:
        """
        层序遍历(保留每层的最后一个元素)
        :param root:
        :return:
        """
        res = []
        if not root:
            return res
        queue = [root]
        while queue:
            n = len(queue)
            while n > 0:
                if n == 1:
                    res.append(queue[0].val)
                if queue[0].left:
                    queue.append(queue[0].left)
                if queue[0].right:
                    queue.append(queue[0].right)
                del queue[0]
                n -= 1
        return res

    def rightSideView(self, root: TreeNode) -> List[int]:
        return self.rightSideView2(root)


if __name__ == "__main__":
    #     3
    #    / \
    #   9  20
    #     /  \
    #    15   7
    root = TreeNode(3)
    root.left, root.right = TreeNode(9), TreeNode(20)
    root.right.left, root.right.right = TreeNode(15), TreeNode(7)
    print(Solution().rightSideView(root))
    #         1
    #        /  \
    #       2    3
    #        \    \
    #         5    4
    root = TreeNode(1)
    root.left, root.right = TreeNode(2), TreeNode(3)
    root.left.right, root.right.right = TreeNode(5), TreeNode(4)
    print(Solution().rightSideView(root))
